package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * 87. 扰乱字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/6 22:14
 */
public class IsScramble {


    public static void main(String[] args) {
        IsScramble test = new IsScramble();

        // true
        String str1 = "great";
        String str2 = "rgeat";

        // true
//        String str1 = "a";
//        String str2 = "a";

        // true
//        String str1 = "abb";
//        String str2 = "bab";

        // false
//        String str1 = "abcde";
//        String str2 = "caebd";

        // false
//        String str1 = "adfadgsadfasdgffsdhgfdgdfssadf";
//        String str2 = "errgfdsagfhasdfsdarerdsfdgsaas";

        boolean scramble = test.isScramble(str1, str2);
        System.out.println(scramble);

    }

    public boolean isScramble(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        return find(arr1, 0, s2.length() - 1, arr2, 0, s2.length() - 1);
    }

    private boolean find(char[] arr1, int st1, int end1, char[] arr2, int st2, int end2) {
        int l = end2 - st2;
        if (l == 0) {
            return arr1[st1] == arr2[st2];
        }
        if (l == 1) {
            return (arr1[st1] == arr2[st2] && arr1[end1] == arr2[end2]) || (arr1[end1] == arr2[st2] && arr1[st1] == arr2[end2]);
        }
        int[] as = new int[26];
        int[] lefts = new int[26];
        int[] rights = new int[26];
        for (int i = 0; i < l; i++) {
            as[arr2[i + st2] - 'a']++;
            lefts[arr1[i + st1] - 'a']++;
            rights[arr1[end1 - i] - 'a']++;
            boolean flag = check(as, lefts);
            if (flag) {
                boolean b = find(arr1, st1, st1 + i, arr2, st2, st2 + i);
                if (b) {
                    b = find(arr1, st1 + i + 1, end1, arr2, st2 + i + 1, end2);
                }
                if (b) {
                    return true;
                }
            }
            flag = check(as, rights);
            if (flag) {
                boolean b = find(arr1, end1 - i, end1, arr2, st2, st2 + i);
                if (b) {
                    b = find(arr1, st1, end1 - i - 1, arr2, st2 + i + 1, end2);
                }
                if (b) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(int[] as, int[] bs) {
        for (int i = 0; i < 26; i++) {
            if (as[i] != bs[i]) {
                return false;
            }
        }
        return true;
    }
}
